#include<iostream>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<math.h>
#include<assert.h>
#include<stack>
#include<vector>
#include<set>
#include<unordered_map>
using namespace std;
enum color
{
    black,
    red
};
template<class k,class v>
class rbtreenode
{
public:
    typedef rbtreenode<k, v> node;
    color _color;
    pair<k, v> _kv;
    node* _left;
    node* _right;
    node* _parent;
    rbtreenode(const pair<k,v>& kv):
        _left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _kv(kv)
    {}
};
template<class k,class v>
class rbtree
{
    typedef rbtreenode<k,v> node;
public:
    bool insert(const pair<k, v>& kv)
    {
        node* newnode = new node(kv);
        newnode->_color = red;
        if (_root == nullptr) {
            _root = newnode;
            _root->_color = black;
            return true;
        }
        node* parent = nullptr;
        node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else return false;
        }
        if (parent->_kv.first > kv.first)
            parent->_left = newnode;
        else
            parent->_right = newnode;
        newnode->_parent = parent;
        while (parent && parent->_color == red)
        {
            node* g = parent->_parent;
            node* u = g->_left == parent ? g->_right : g->_left;
            // 情况1: 叔叔存在且为红
            if (u && u->_color == red)
            {
                // 颜色翻转
                g->_color = red;
                u->_color = black;
                parent->_color = black;

                // 向上递归：当前节点变为祖父
                newnode = g;
                parent = g->_parent;
            }
            else // 情况2: 叔叔不存在或为黑
            {
                if (parent == g->_left)
                {
                    if (newnode == parent->_left) // LL
                    {
                        RotateR(g);
                        parent->_color = black;
                        g->_color = red;
                    }
                    else // LR
                    {
                        RotateLR(g);
                        newnode->_color = black;
                        g->_color = red;
                    }
                }
                else
                {
                    if (newnode == parent->_right) // RR
                    {
                        RotateL(g);
                        parent->_color = black;
                        g->_color = red;
                    }
                    else // RL
                    {
                        RotateRL(g);
                        newnode->_color = black;
                        g->_color = red;
                    }
                }
                break; // 旋转后必须退出
            }
        }
        _root->_color = black; // 确保根为黑
        return true;
    }
    void inorder()//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
    {
        inorder(_root);
    }
private:
    void inorder(node* cur)//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
    {
        if (cur == nullptr) return;
        inorder(cur->_left);             // 先递归遍历左子树
        cout << cur->_kv.first << ':' << cur->_kv.second << endl;       // 再输出当前节点值
        inorder(cur->_right);            // 最后递归遍历右子树
    }
    node* _root = nullptr;
    void RotateR(node* parent)
    {
        node* subL = parent->_left;
        node* subLR = subL->_right;

        subL->_right = parent;//先改变subL相应的指针
        subL->_parent = parent->_parent;

        if (parent == _root) _root = subL;
        else
        {
            if (parent->_parent->_left == parent)//改parent->_parent得到指针
                parent->_parent->_left = subL;
            else parent->_parent->_right = subL;
        }

        parent->_parent = subL;//再改parent相应的指针
        parent->_left = subLR;

        if (subLR) subLR->_parent = parent;//修改subLR的指针
    }
    void RotateL(node* parent)
    {
        node* subR = parent->_right;
        node* subRL = subR->_left;

        //修改subR的相关指针
        subR->_parent = parent->_parent;
        subR->_left = parent;

        if (parent == _root) _root = subR;
        else
        {
            if (parent->_parent->_left == parent)
                parent->_parent->_left = subR;
            else parent->_parent->_right = subR;
        }

        if (subRL) subRL->_parent = parent;//修改subRL的相关指针

        parent->_right = subRL;//修改parent相应的指针
        parent->_parent = subR;//注意这里修改了parent的parent，因为原parent的parent也有指针需要修改，所以要么用变量记录一下，要么将paarent的parent的修改放到后面
    }
    void RotateLR(node* parent)
    {
        node* subl = parent->_left;
        node* sublr = subl->_right;
        RotateL(subl);
        RotateR(parent);
    }
    void RotateRL(node* parent)
    {
        node* subr = parent->_right;
        node* subrl = subr->_left;
        RotateR(subr);
        RotateL(parent);
    }
};
int main()
{
    rbtree<int, int> t1;
    for (int i = 0; i < 10; i++)
        t1.insert({ i,i });
    t1.inorder();
    return 0;
}